SVMs and the Kernel Trick

SVM

首先，SVM的目标是找到一个超平面（hyperplane），使得它能将数据分成两类，并且距离超平面最近的点到超平面的距离最大化。

举个具体的例子：
现在我们有一个超平面：

$$2x_1 + 3x_2 - 6 = 0$$

即 $\beta = [2, 3]$, $b = -6$

(1) 其中一个支持向量位于：$x = (4, 1)$

(2) 所以超平面法向量L2范数(即长度)为：

$$\|\beta\|_2 = \sqrt{2^2 + 3^2} = \sqrt{13}$$

(3) 该支持向量到超平面的距离为：

$$d = \frac{2*4 + 3*1 - 6}{\sqrt{13}} = \frac{5}{\sqrt{13}}$$

(4) $\alpha$:
$\alpha$ 的含义就是 $d$ 的长度, 即 $\frac{5}{\sqrt{13}}$

(5) 而向量 $d$ :

$$d = \alpha \frac{\beta}{||\beta||} = \frac{5}{\sqrt{13}} * \frac{[2, 3]}{\sqrt{13}} = \frac{5}{13} * [2, 3] = [\frac{10}{13}, \frac{15}{13}]$$

Hinge Loss

介绍一个新loss function：Hinge Loss(合页损失)

举个栗子:
给定一个样本点 $x_i$, 它的真实标签是 $y_i = -1$, 预测标签是 $f(x_i) = \beta^T x_i = 0.5$, 那么它的Hinge Loss为：

$$h(x, y, \beta) = max(0, 1 - y_i f(x_i)) = max(0, 1 - (-1) * 0.5) = 1.5$$

你看，如果预测值不是0.5而是-1.2，那么Hinge Loss就是0了。
所以：

• $y_i(\beta^T x_i) \ge 1$, Hinge Loss = 0 -> 分类足够好，不需要优化
• $y_i(\beta^T x_i) < 1$, Hinge Loss > 0 -> 损失增大，迫使调整边界，提高分类精度

所以HL才适用于SVM，因为优化目标就是最大化边界。

Math Optimization

To balance between maximizing accuracy and maximizing margin, fit the hyperparameter $\Lambda$:

SVM loss function:

$$\min_{\beta} \|\beta\|_2 + \lambda h(x, y, \beta)$$

Gradient Descent优化推导：

上面式子拆开来：

$$=> \min_{\beta} \|\beta\|_2 + \lambda \frac{1}{N} \sum_{i=1}^{N} max(0, 1 - y_i \beta^T x_i)$$ $$=> \min_{\beta} \frac{1}{N} \sum_{i=1}^{N} [ \ \|\beta\|_2 + \lambda max(0, 1 - y_i \beta^T x_i) \ ]$$

那最后对 $\beta$ 求偏导：

$$\frac{\partial}{\partial \beta} = \frac{1}{N} \sum_{i=1}^{N} \begin{cases} \beta, & 1 - y_i (\beta^T x_i) \leq 0 \\ \beta - \lambda y_i x_i, & \text{otherwise} \end{cases}$$

厉害的来了!! Dual problem optimization

不管别的，总之SVM问题是strong duality的：

所以求maximizing accuracy和求maximizing margin(i.e. minimizing $\|\beta\|_2$)是等价的。

拉格朗日乘子

拉格朗日乘子法将约束问题转化为无约束问题。

目前，我们的约束是：

$$y_i(\beta^T x_i + b) \ge 1$$

为了消除这个约束，我们引入拉格朗日乘子 $\alpha_i \ge 0$来代表这个约束的惩罚程度。
于是我们有拉格朗日函数：

$$L(\beta, b, \alpha) = \frac{1}{2} \|\beta\|_2^2 - \sum_{i=1}^{N} \alpha_i [ \ y_i(\beta^T x_i + b) - 1 \ ]$$

将原问题变换成对偶问题

SVM采用拉格朗日对偶性来求解，即我们需要先对 $\beta$ 和 $b$ 求最小，再对 $\alpha$ 求最大。

1. 对 $\beta$： $$\frac{\partial L}{\partial \beta} = \beta - \sum_{i=1}^{N} \alpha_i y_i x_i = 0$$

$$=> \beta = \sum_{i=1}^{N} \alpha_i y_i x_i$$

2. 对 $b$： $$\frac{\partial L}{\partial b} = - \sum_{i=1}^{N} \alpha_i y_i = 0$$

$$=> \sum_{i=1}^{N} \alpha_i y_i = 0$$

3. 将 $\beta = \sum\_{i=1}^{N} \alpha_i y_i x_i$ 代入 $L(\beta, b, \alpha)$, 得到对偶问题:

$$\max_{\alpha} \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j x_i^T x_j$$

线性不可分？

Q: 碰到上图中这种非线性可分的数据点集怎么办？
A:

1. 升维：将数据点升维到高维空间，变成线性可分的
2. kernel trick：直接在低维空间中计算高维空间的内积

讲半天没看懂，直接上实例：

假设现在我们有四个数据点线性不可分：
Sample 1 = (1, -1)
Sample 2 = (3, -1)
Sample 3 = (1.4, 1)
Sample 4 = (2.2, 1)
没法被直线分割，所以我们将它们映射到高维空间去被超平面分割：
定义一个映射：

$$\phi(x) = \begin{bmatrix} x^2 \\ x^3 \end{bmatrix}$$

也就是说 $x = 1$ 映射到 $\phi(1) = [1, 1]$, $x = 3$ 映射到 $\phi(3) = [9, 27]$

问题来了

由于前面我们已经知道了SVM的对偶问题中，无论是 $\beta = \sum*{i=1}^{N} \alpha_i y_i x_i$, 还是最后的对偶问题：$\max*{\alpha} \sum*{i=1}^{N} \alpha_i - \frac{1}{2} \sum*{i=1}^{N} \sum\_{j=1}^{N} \alpha_i \alpha_j y_i y_j x_i^T x_j$，都需要计算 $x_i^T x_j$。

假如我们的映射函数是100维的，那我们在计算内积 $x_i^T x_j$ 的时候就需要计算100*100=10000次了。

所以我们就要用到kernel trick了：

$$K(x_i, x_j) = \phi(x_i)^T \phi(x_j) = (s_i \cdot s_j + r)^d$$

在这个问题中，$r$ 被设定为1，而 $d$ 则是映射的维度，即2。
也就是说，我们可以通过这种方法近似的计算出高维空间的内积：

$$K(x_i, x_j) = (s_i \cdot s_j + 1)^2 = 16$$

番外：RBF (Radial Basis Function) kernel

径向基核：

$$K(x_i, x_j) = e^{-\gamma ||s_i - s_j||^2}$$

这玩意也简单推一下吧（复习的时候忽略也行我估计..）【被自己骗了...考了呃呃啊啊啊啊！！】：

设定 $\sigma = 1/2$, 然后展开：

$$e^{-\frac{1}{2} ||s_i^2 + s_j^2||} e^{s_is_j}$$

$e^{s_is_j}$ 这玩意无穷级数，占比太大了，基本上RBF kernel就近似等于这一个超高项了。
所以RBF kernel用来处理高度非线性数据集，因为它不局限固定阶数。

要喜欢研究就看吧..

番外：Multi-SVM

1. One-vs-One：
   • 两两分类，每次选两个类别，训练一个SVM
   • n个类别，需要训练 $C_n^2$ 个SVM
2. One-vs-Rest：
   • 一个类别对其他所有类别进行分类
   • n个类别，需要训练n个SVM